package org.lql.algo.codecrush.hot100.graphTheory;

/**
 * @author: liangqinglong
 * @date: 2025-09-16 00:49
 * @description: 208. 实现 Trie (前缀树) <a href="https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class Trie {


	TrieNode root;
	public Trie() {
		root = new TrieNode();
	}

	public void insert(String word) {
		TrieNode current = root;
		for (char c : word.toCharArray()) {
			int index = c - 'a';
			if (current.children[index] == null) {
				current.children[index] = new TrieNode();
			}
			current = current.children[index];
		}
		current.isEndOfWord = true;
	}

	public boolean search(String word) {
		TrieNode cur = root;
		for (char c : word.toCharArray()) {
			int index = c - 'a';
			if (cur.children[index] == null) {
				return false;
			}
			cur = cur.children[index];
		}
		return cur != null && cur.isEndOfWord;
	}

	public boolean startsWith(String prefix) {
		TrieNode cur = root;
		for (char c : prefix.toCharArray()) {
			int index = c - 'a';
			if (cur.children[index] == null) {
				return false;
			}
			cur = cur.children[index];
		}
		return cur != null;
	}

	public static class TrieNode {
		private final int ALPHABET_SIZE = 26;
		TrieNode[] children = new TrieNode[ALPHABET_SIZE];
		boolean isEndOfWord;

		public TrieNode() {
			isEndOfWord = false;
		}
	}

	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.insert("apple");
		System.out.println(trie.search("apple"));
		System.out.println(trie.search("app"));
		System.out.println(trie.startsWith("app"));
		trie.insert("app");
		System.out.println(trie.search("app"));
		System.out.println(trie.startsWith("app"));
	}
}
